package algorithm.dynamic;

import java.util.HashMap;
import java.util.Map;

/**
 * leetcode : https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
 * Diffculty: Medium
 *
 * 动态规划
 * 求一个字符串的最长字串的长度，要求没有重复的字符
 * 解答：https://www.jianshu.com/p/61670f0f285f
 *
 * 使用动态规划, 还是递推法
 * 思路：
 *
 * 建立一个map，记录每一个元素上一次出现的位置 lastIndex
 * 建立当前序列，最小子序列的开始位置 startIndex
 *
 * 以arr[i] 为结尾的序列，其最长子序列为：
 *      以 arr[i-1] 为结尾的最长子序列 再判断是否加上 arr[i]
 *          如果 arr[i] 的 lastIndex 不存在，或者在 startIndex之前，那么当前长度为 i-startIndex+1;
 *          否则 改变startIndex 为 lastIndex+1。当前长度为 i-startIndex+1;
 *
 * @Author Antony
 * @Since 2018/6/25 10:52
 */
public class LongestSubString {

    public static void main(String[] args) {
        String s1 = "abcabcbb";     // answer "abc"
        String s2 = "bbbbb";        // answer "b";
        String s3 = "pwwkew";       // answer "wke"
        String s4 = "au";           // answer "au"
        String s5 = "dvdf";         // answer "vdf"

//        System.out.println(exhaustion(s1));
//        System.out.println(exhaustion(s2));
//        System.out.println(exhaustion(s3));
//        System.out.println(exhaustion(s4));
//        System.out.println(exhaustion(s5));


        System.out.println(dynamic(s1));
        System.out.println(dynamic(s2));
        System.out.println(dynamic(s3));
        System.out.println(dynamic(s4));
        System.out.println(dynamic(s5));

    }

    /**
     * 动态规划，通过leetcode, 57ms
     * @param s
     * @return
     */
    public static int dynamic(String s){
        if(s.length() == 0){
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();

        int maxLength = 0;
        int subStrStartIndex = 0;
        Integer charIndex;
        int currLength;
        for(int i=0; i<chars.length; i++){
            charIndex = map.get(chars[i]);
            if(charIndex != null && charIndex >= subStrStartIndex){
                subStrStartIndex = charIndex + 1;
            }

            currLength = i-subStrStartIndex + 1;
            maxLength = maxLength > currLength ? maxLength : currLength;
            map.put(chars[i], i);
        }

        return maxLength;
    }

    /**
     * 穷举法，没有通过leetcode 时间太长
     * @param s
     * @return
     */
    public static int exhaustion(String s) {
        if(s.length() == 0){
            return 0;
        }
        char[] charArray = s.toCharArray();
        int maxLength = 1;
        int curr;
        for(int i=0; i<charArray.length; i++){
            for(int j=1; j<charArray.length; j++){
                if(containsChar(charArray, i, j-1, charArray[j])){
                    break;
                }else{
                    curr = j-i+1;
                    if(maxLength < curr){
                        maxLength = curr;
                    }
                }
            }
        }

        return maxLength;
    }

    private static boolean containsChar(char[] chars, int start, int end, char c){
        for(int i=start; i<=end; i++){
            if(c == chars[i]){
                return true;
            }
        }

        return false;
    }
}
